Conventional IP networking equipment hardware utilizes one of two general approaches for routing IP packets. In the first approach (hereinafter, “LPM mode” or “the LPM approach”), the IP destination address of each packet is used as a key to search a hardware-based longest prefix match (LPM) table containing variable length address prefixes. A match in the hardware LPM table results in an index into an IP adjacency table where nexthop forwarding information needed to successfully route the packet is obtained. In the first approach, the hardware LPM table can be populated using one or more routing protocols which exchange information with neighboring IP packet forwarding devices or populated via configuration.
In the second approach (hereinafter, “IPFDB mode” or “the IPFDB approach”), the IP destination address of each packet is used as a key to search a hardware-based IP host forwarding database (IPFDB) populated with the IP addresses of active hosts. It is appreciated that active hosts may include both directly attached hosts and hosts remotely located on the other side of the network when operating in IPFDB mode. A match in the hardware IPFDB results in the nexthop forwarding information needed to successfully route the packet. In the second approach, the IP addresses of active hosts are populated in the IPFDB on an “on demand” basis. That is, when a stream for a given host starts up, its IP address is initially not stored in the IPFDB and must be slowpath processed, where slowpath processing includes processing the packet using a central processing unit (CPU). Successful slowpath processing of the packet results in the IP addresses of active hosts being programmed into the hardware IPFDB for subsequent packets.
For example, referring to FIG. 1, I/O modules 102A and 106A may operate in either LPM mode or IPFDB mode. In LPM mode, LPM tables 200 and 204 may be populated with entries corresponding to variable length address prefixes and next hops for reaching destinations and IPFDBs 202 and 206 may be populated with full-length 32- or 128-bit host entries. In IPFDB mode, LPM tables 200 and 204 and IPFDBs 202 and 206 may be populated with full-length 32- or 128-bit host entries. Additionally, I/O modules 102A-102C and 106A-106B may be operated in a “hybrid” mode where, for each I/O module, the IPFDB may be populated with full address entries for directly connected hosts and the LPM table may be populated with a mixture of variable length prefixes and full host addresses. Additional details regarding this aspect are described in U.S. patent application Ser. No. 11/317,665, filed on Dec. 23, 2005, and U.S. patent application Ser. No. 11/644,701, filed on Dec. 22, 2006, the disclosures of which are incorporated by reference herein in their entireties.
One advantage of the LPM approach is that an almost limitless number of host end-stations can communicate through the switch without slowpath intervention when the entire routing table can be contained in the available hardware LPM table. In contrast, one advantage of the IPFDB approach is that routing may be faster when the route table doesn't fit in the hardware LPM table (e.g. for small numbers of hosts). For example, by routing packets based on exact match lookups in a hardware-based IPFDB located on each I/O module, less memory and CPU resources may be used to slowpath process packets. In other words, the LPM approach is more advantageous when the entire routing table can be contained in the available hardware LPM table, while the IPFDB approach is more advantageous when the entire routing table cannot be contained in the available hardware LPM table.
When producing cost-sensitive networking equipment, the hardware LPM table size can be limited for some applications. In one exemplary scenario, an edge module may support 512 LPM IPv4 routes and 2K IPv4 hosts and an aggregation module may support 512,000 LPM IPv4 routes and 16,000 IPv4 hosts. Next, consider a network with a control plane routing table size of 250,000 IPv4 routes and 1,000 directly attached IPv4 hosts. It may be appreciated that this entire routing table cannot be contained in the available hardware LPM table of edge modules 102A-102C yet can be entirely contained in the LPM table of aggregator modules 106A-106B. As such, IPFDB-mode routing may be desirable for edge modules 102A-102C in order to avoid unnecessary slowpath processing. Because edge module cannot store 250,000 routes in an LPM table size of 512, it would serve little purpose to populate just 512 out of 250,000 routes (i.e., 0.2%) into this HW table. Thus, the IPFDB approach requires less memory and less CPU power in the packet forwarding equipment by only maintaining a cache of active hosts, not the entire routing table.
In contrast, LPM-mode routing may be desirable for aggregator modules 106A-106B because the routing table is within the hardware limits because all directly connected hosts may be routed to using hardware IPFDBs and all hosts connected via a gateway may be routed to using hardware LPM tables, without the need for slowpath processing packets.
One problem associated with conventional packet forwarding devices is that they may use inefficient approaches for some I/O modules under certain conditions. For example, in packet forwarding device 100, if I/O modules 102A and 106A are operated in LPM mode (the default), then low-capacity I/O module 102A may store a virtually meaningless fraction of the number of routes, adding no performance benefit to packet forwarding device 100.
Another problem is that some packet forwarding equipment may not have enough memory to hold the entire routing table in software, nor enough CPU power to handle all the route add and delete operations. For example, conventional LPM mode operation requires more memory and CPU power to handle route add and delete operations, while IPFDB mode does not because, instead, IPFDB mode only maintains a cache of active hosts, not the entire routing table. As mentioned above, in scenarios in which IPFDB mode is desirable, but not used, the conventional packet forwarding devices may operate sub-optimally.
Accordingly, there exists a need for improved methods, systems, and computer readable media for more efficiently utilizing the hardware-based LPM table and IPFDB in IP packet forwarding devices.